package leetcode;

import util.Tree;
import util.TreeNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0112.java
 * @Author : WangRuoyu
 * @Date 2023/10/23 12:10
 */

public class Q0112 {
    private boolean dfs(TreeNode node, int target, int sum) {
        if (node.left == null && node.right == null) return sum + node.val == target;
        boolean res = false;
        if (node.left != null) res = dfs(node.left, target, sum + node.val);
        if (res) return res;
        if (node.right != null) res = dfs(node.right, target, sum + node.val);
        return res;
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        return root != null && dfs(root, targetSum, 0);
    }

    public static void main(String[] args) {
        Q0112 sl = new Q0112();
        String[] tree = {"5", "4", "11", "7", null, null, "2", null, null, null, "8", "13", null, null, "4", null, "1", null, null};
        TreeNode root = Tree.createTreeByPreorder(tree);
//        Tree.traversal(root);
        int target = 22;
        System.out.println(sl.hasPathSum(root, target));
    }
}